package cn.org.guhao.practice.go.util;

import cn.org.guhao.practice.go.model.IntegerTreeNode;
import cn.org.guhao.practice.go.model.TreeNode;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

/**
 * 二叉树工具类
 * @author guhao
 */
public class BinaryTreeUtils {

  private static final Logger logger = LoggerFactory.getLogger(BinaryTreeUtils.class);

  private BinaryTreeUtils(){
    logger.error("[{}]工具类保护",StringUtils.class.getName());
  }

  public static String levelTraverse(TreeNode node){
    StringBuilder sortData = new StringBuilder();
    LinkedList<TreeNode> nodeLinkedList = new LinkedList<TreeNode>();
    nodeLinkedList.add(node);
    while (nodeLinkedList.size() != 0){
      TreeNode tn = nodeLinkedList.poll();
      sortData.append(tn.getData());
      if(tn.getLeft() != null){
        nodeLinkedList.add(tn.getLeft());
      }
      if(tn.getRight() != null){
        nodeLinkedList.add(tn.getRight());
      }
    }
    return sortData.toString();
  }

  public static List<Integer> buildValues(IntegerTreeNode node){
    List<Integer> values = new ArrayList<Integer>();
    Set<Integer> valueSet = new HashSet<Integer>();
    LinkedList<IntegerTreeNode> nodeLinkedList = new LinkedList<IntegerTreeNode>();
    nodeLinkedList.add(node);
    while (nodeLinkedList.size() != 0){
      IntegerTreeNode tn = nodeLinkedList.poll();
      if(!valueSet.contains(tn.getValue())) {
        values.add(tn.getValue());
        valueSet.add(tn.getValue());
      }

      if(tn.getLeft() != null){
        nodeLinkedList.add(tn.getLeft());
      }
      if(tn.getRight() != null){
        nodeLinkedList.add(tn.getRight());
      }
    }
    return values;
  }

  public static int kthSmallest(IntegerTreeNode node,int k){
    List<Integer> values = buildValues(node);
    Collections.sort(values);
    return values.get(k-1);
  }

  /**
   * 二叉树反转
   * @param node
   * @return
   */
  public static IntegerTreeNode reverse(IntegerTreeNode node){
    LinkedList<IntegerTreeNode> nodeLinkedList = new LinkedList<IntegerTreeNode>();
    nodeLinkedList.add(node);
    while (nodeLinkedList.size() != 0){
      IntegerTreeNode tn = nodeLinkedList.poll();

      IntegerTreeNode exchangeLeft = tn.getLeft();
      IntegerTreeNode exchangeRight = tn.getRight();

      if(exchangeLeft != null){
        nodeLinkedList.add(exchangeLeft);
      }
      if(exchangeRight != null){
        nodeLinkedList.add(exchangeRight);
      }
      tn.setLeft(exchangeRight);
      tn.setRight(exchangeLeft);
    }
    return node;
  }

  /**
   * 打印二叉树
   * @param node
   * @return
   */
  public static void print(IntegerTreeNode node){
    LinkedList<IntegerTreeNode> nodeLinkedList = new LinkedList<IntegerTreeNode>();
    nodeLinkedList.add(node);
    IntegerTreeNode last = node;
    IntegerTreeNode nlast = node;
    while (!nodeLinkedList.isEmpty()) {
      IntegerTreeNode tn = nodeLinkedList.poll();
      System.out.print(tn.getValue());
//      if(nodeLinkedList.size() == 0){
//        System.out.print("\n");
//      }
      if(tn.getLeft() != null){
//        System.out.print("/");
        nodeLinkedList.add(tn.getLeft());
        nlast = tn.getLeft();
      }
      if(tn.getRight() != null){
//        System.out.print("\\");
        nodeLinkedList.add(tn.getRight());
        nlast = tn.getRight();
      }
      if (last == tn) {
        System.out.println();
        last = nlast;
      }
    }

  }

  /**
   * 计算满二叉树深度
   * @param sum 总和
   * @return  二叉树深度
   */
  public static int calcFullDeep(int sum){
    int deep = 1;
    int calcSum = 1;
    int lastNum = 1;
    while (true){
      deep++;
      lastNum = lastNum * 2;
      calcSum = calcSum + lastNum;
      if(calcSum > sum){
        return deep;
      }
      if (deep > 10000){
        return deep;
      }
    }
  }


}
